﻿//https://leetcode.cn/problems/duplicate-zeros/submissions/615799653/

class Solution {
public:
    void duplicateZeros(vector<int>& arr)
    {
        int cur = 0, dest = -1, n = arr.size();

        //找到最后一个数
        while (cur < n)
        {
            if (arr[cur])
                dest++;
            else
                dest += 2;
            if (dest >= n - 1)
                break;
            cur++;
        }

        //处理边界情况
        if (dest == n)
        {
            arr[n - 1] = 0;
            dest -= 2;
            cur--;
        }

        //复写
        while (cur >= 0)
        {
            if (arr[cur])
                arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }

    }
};

//https://leetcode.cn/problems/happy-number/submissions/615802718/

class Solution {
public:
    //计算每位数字的平方和
    int bitsum(int x)
    {
        int sum = 0;
        while (x)
        {
            int temp = x % 10;
            sum += temp * temp;
            x /= 10;
        }
        return sum;
    }
    bool isHappy(int n)
    {
        //快慢指针
        int slow = n, fast = bitsum(n);
        while (slow != fast)
        {
            slow = bitsum(slow);
            fast = bitsum(bitsum(fast));
        }
        return slow == 1;
    }
};

//https://leetcode.cn/problems/container-with-most-water/submissions/615804465/

class Solution {
public:
    int maxArea(vector<int>& height)
    {
        int left = 0, right = height.size() - 1, ret = 0;
        while (left < right)
        {
            int sum = min(height[left], height[right]) * (right - left);
            ret = max(sum, ret);
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return ret;
    }
};

//https://leetcode.cn/problems/valid-triangle-number/description/

class Solution {
public:
    int triangleNumber(vector<int>& nums)
    {
        //优化
        sort(nums.begin(), nums.end());
        int  ret = 0;
        for (int i = nums.size() - 1; i >= 2; i--)
        {
            int left = 0, right = i - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }

        return ret;
    }
};

//https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/submissions/615811614/

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target)
    {
        int left = 0, right = price.size() - 1;
        while (left < right)
        {
            int sum = price[left] + price[right];
            if (sum > target)
                right--;
            else if (sum < target)
                left++;
            else
                return { price[left],price[right] };
        }

        return { -1,-1 };
    }
};
